package leetcode.median;

import java.util.LinkedList;
import java.util.Queue;

public class $994_OrangesRotting {
    public int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0){return -1;}
        int row = grid.length;
        int col = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int cnt = 0;
        for (int i = 0;i < row;i++) {
            for (int j = 0;j < col;j++) {
                if (grid[i][j] == 1) {
                    cnt++;
                } else if(grid[i][j] == 2){
                    queue.add(new int[]{i, j});
                }
            }
        }
        int res = 0;
        while (!queue.isEmpty() && cnt > 0){
            res++;
            int n = queue.size();
            for(int i = 0;i < n;i++){
                int[] colOrange = queue.poll(); // 腐烂的橘子
                int r = colOrange[0];
                int c = colOrange[1];
                if (r - 1 >= 0 && grid[r - 1][c] == 1) {
                    // 感染上面
                    grid[r - 1][c] = 2;
                    cnt--;
                    queue.add(new int[]{r - 1, c});
                }
                if (r + 1 < row && grid[r + 1][c] == 1){
                    // 感染下面
                    grid[r + 1][c] = 2;
                    cnt--;
                    queue.add(new int[]{r + 1, c});
                }
                if (c - 1 >= 0 && grid[r][c - 1] == 1){
                    grid[r][c - 1] = 2;
                    cnt--;
                    queue.add(new int[]{r, c - 1});
                }
                if (c + 1 < col && grid[r][c + 1] == 1){
                    grid[r][c + 1] = 2;
                    cnt--;
                    queue.add(new int[]{r, c + 1});
                }
            }
        }
        return cnt == 0 ? res : -1;
    }

    public int orangesRotting1(int[][] grid) {


        return 0;
    }
}
